<<<<<<< HEAD:cxx/algorithm/src/maxValue.cc
//
// Created by bleedingfight on 2020/7/4.
//

#include "maxValue.h"
int maxValue(std::vector<std::vector<int>>& grid){
    const int rows = grid.size();
    if(rows == 0)
        return 0;
    const int cols = grid[0].size();
    if(cols == 0)
        return 0;
    std::vector<int>sum_dp = std::vector<int>(cols,0);
    for(int row =0;row<rows;row++){
        for(int col=0;col<cols;col++){
            if(col == 0 && row == 0)
                sum_dp[col] = grid[row][col];
            else if(row == 0 && col!=0)
                sum_dp[col] = grid[row][col]+sum_dp[col-1];
            else if(row !=0 && col==0)
                sum_dp[col] = grid[row][col]+sum_dp[col];
            else
            {
                int left = sum_dp[col-1];
                int upper = sum_dp[col];
                if(left>upper){
                    sum_dp[col]=left+grid[row][col];
                } else{
                    sum_dp[col]=upper+grid[row][col];
                }
            }
        }
    }
    return sum_dp[cols-1];
=======
#include "maxValue.h"
// 最容易理解的递归处理
int max_value(vector<vector<int>>& a,int r,int c)
{
    //为了避免二维矩阵无数据出错
    assert(a.size()>0);
    int Row = a.size();
    int Col = a[0].size();
    if(r == Row-1)
        return a[r][c];
    else
        return max_value(a,r+1,c)+max(a[r+1][c],a[r+1][c+1]);
}
// 使用原数据存储和找到最大和
int max_value1(vector<vector<int>>& a,int r, int c){
    assert(a.size()>0);
    int Row = a.size();
    int Col = a[0].size();
    for(int r = Row-2;r>=0;r--)//-2是为了防止r+1溢出
    {
        for(int c=0;c<Col-1;c++)
            a[r][c] = a[r][c]+max(a[r+1][c],a[r+1][c+1]);
    }
    return a[0][0];
>>>>>>> dev:cxx/algorithm/common/src/maxValue.cc
}
